#!/usr/bin/python

from __future__ import with_statement
import threading
import sys

# DICTIONARY_FILE = "twl06.txt" # "/var/tmp/twl06.txt"
DICTIONARY_FILE = "/var/tmp/twl06.txt"

def calculateEditDistance(str1, str2):
   # initialize matrix with initial values
   str1len, str2len = len(str1), len(str2)
   M = [
      [n] + (list(range(1,str2len+1)) if n == 0 else [0] * (str2len)) 
      for n in range(str1len+1)
   ]

   # start computing the distance matrix
   for i in range(str1len):
      for j in range(str2len):
         # we need to shift the index by one because the matrix row+1 and col+1
         # to calculate the base cases
         ii, jj = i+1, j+1
         delCost = M[ii-1][jj] + 1
         insCost = M[ii][jj-1] + 1
         replOrMatchCost = M[ii-1][jj-1] + (0 if str1[i] == str2[j] else 1)
         M[ii][jj] = min(delCost, insCost, replOrMatchCost)

   # result is at the corner of the matrix
   return M[str1len][str2len]

def parse_file_to_word_list(thefile):
   words = [ ]
   for line in thefile:
      words.extend(line.split())
   return words

class Dictionary:
   def __init__(self, filename):
      with open(filename) as thefile:
         self.data = [line.strip().lower() for line in thefile]

   def findMinimumWithinRange(self, word, startIndex, currentMin, nextIndexFunc):
      result = currentMin
      i = startIndex
      while self.data[i][0] == word[0]:
         comp = self.data[i], self.wordDistanceAtIndex(i, word)
         if comp[1] < result[1]:
            result = comp
         i = nextIndexFunc(i)
      return result

   def findClosestMatch(self, word):
      # find the word and its index from dictionary first. If found match, the
      # distance is surely 0
      index, found = self.findIndexOfWord(word)
      if found: 
         return self.data[index], 0


      # result = self.data[index], self.wordDistanceAtIndex(index, word)
      # outmap = { }
      # def searchup(self, outmap): 
      #    outmap['resultup'] = self.findMinimumWithinRange(word, index-1, result, lambda i: i-1)
      # upthread = threading.Thread(target=searchup, args=(self, outmap))
      # upthread.start()
      # def searchdown(self, outmap): 
      #    outmap['resultdown'] = self.findMinimumWithinRange(word, index-1, result, lambda i: i-1)
      # downthread = threading.Thread(target=searchdown, args=(self, outmap))
      # downthread.start()

      # upthread.join()
      # downthread.join()

      # return (outmap['resultup'] if outmap['resultup'][1] < outmap['resultdown'][1] 
      #                            else outmap['resultdown'])

      # searching backward and forward for words beginning with the same letter
      result = self.data[index], self.wordDistanceAtIndex(index, word)
      result = self.findMinimumWithinRange(word, index-1, result, lambda i: i-1)
      result = self.findMinimumWithinRange(word, index+1, result, lambda i: i+1)
      return result

   def findIndexOfWord(self, word):
      # do the binary search to either find the match word or the index
      # where the word should be
      lowerbound, upperbound = 0, len(self.data)
      while (upperbound - lowerbound) > 1:
         midpoint = lowerbound + ((upperbound - lowerbound) // 2)
         target = self.data[midpoint]
         if word == target:
            return midpoint, True
         elif word > target:
            lowerbound = midpoint
         else:
            upperbound = midpoint

      # if reach here, it doesn't find it. Just return the last midpoint
      return midpoint, False

   def wordDistanceAtIndex(self, index, word):
      return calculateEditDistance(word, self.data[index])


def main(dictFilename, dataFilename):
   d = Dictionary(dictFilename)
   with open(dataFilename) as thefile:
      words = parse_file_to_word_list(thefile)

   minchanges = 0
   for w in words:
      minchanges += d.findClosestMatch(w)[1]
   print minchanges

if __name__ == '__main__':
   main(DICTIONARY_FILE, sys.argv[1])
   
